Stepping numbers [Precompute, Binary Search]

Time: O(LogK + R); Space: O(K); medium

Given two integers N and M, find all the stepping numbers in range [N, M]. A number is called stepping number if all adjacent digits have an absolute difference of 1. 321 is a Stepping Number while 421 is not.

Example 1:

Input : n = 0, m = 21

Output : 0 1 2 3 4 5 6 7 8 9 10 12 21

Example 2:

Input : n = 10, m = 15

Output : 10, 12

import bisect

class Solution1(object):
    """
    Time:  O(k + r), r is the size of result
    Space: O(k), k is the size of stepping numbers in [0, high]
    """
    def countSteppingNumbers(self, low, high):
        """
        :type low: int
        :type high: int
        :rtype: List[int]
        """
        result = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
        for i in range(1, high):
            if result[-1] >= high:
                break
            d1 = result[i]%10 - 1
            if d1 >= 0:
                result.append(result[i]*10 + d1)
            d2 = result[i]%10 + 1
            if d2 <= 9:
                result.append(result[i]*10 + d2)
        result.append(float("inf"))
        lit = bisect.bisect_left(result, low);
        rit = bisect.bisect_right(result, high);
        return result[lit:rit]

s = Solution1()
n = 0
m = 21
assert s.countSteppingNumbers(n, m) == [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 21]
n = 10
m = 15
assert s.countSteppingNumbers(n, m) == [10, 12]

See also:

https://www.lintcode.com/problem/stepping-numbers

https://leetcode.com/problems/stepping-numbers